package leetcode.code0450;

import leetcode.IDebug;
import leetcode.helper.H;
import leetcode.helper.tree.TreeArray;
import leetcode.helper.tree.TreeNode;

public class Solution3 implements IDebug {

	public TreeNode deleteNode(TreeNode root, int key) {
		// 目标，目标上级，目标next，目标next上级
		TreeNode[] find = this.deleteNode(root, key, null);
		if (find == null) {
			return root;
		}
		TreeNode kn = find[0], knr = find[1];
		if (kn.left == null && kn.right == null) {
			// 如果删除的目标是叶子
			if (knr == null) {
				// 没有上级
				return null;
			} else {
				if (knr.val > kn.val) {
					knr.left = null;
				} else {
					knr.right = null;
				}
				return root;
			}
		}
		TreeNode[] nexts = this.findNext(root, kn.val, null);
		if (nexts == null) {
			if (knr == null) {
				return root.left;
			} else {
				knr.right = null;
				return root;
			}
		}
		TreeNode next = nexts[0], nextp = nexts[1];
		if (next.left != null || next.right != null) {
			// next需要替换
			root = this.deleteNode(root, next.val);
		}
		// 叶子节点被删除，中间其它只是被替换
		if (nextp != null && nextp.val > next.val && nextp.left != null && nextp.left.val == next.val) {
			nextp.left = null;
		} else if (nextp != null && nextp.val < next.val && nextp.right != null && nextp.right.val == next.val) {
			nextp.right = null;
		}
		TreeNode ans = null;
		if (knr != null) {
			// 非根
			if (knr == next) {
				next.left = kn.left;
			} else {
				if (knr.val > kn.val) {
					knr.left = next;
				} else {
					knr.right = next;
				}
				next.left = kn.left;
				next.right = kn.right;
			}
			ans = root;
		} else {
			// n换根
			if (next == kn.right) {
				next.left = kn.left;
			} else {
				next.left = kn.left;
				next.right = kn.right;
			}
			ans = next;
		}
		return ans;
	}

	// 找到val下一个节点和其上级节点
	private TreeNode[] findNext(TreeNode root, int val, TreeNode myRoot) {
		if (root == null) {
			return null;
		}
		TreeNode ans = null;
		TreeNode p = null;
		if (root.val > val) {
			ans = root;
			p = myRoot;
			TreeNode[] ans1 = this.findNext(root.left, val, root);
			if (ans1 != null && ans1[0].val < ans.val) {
				ans = ans1[0];
				p = ans1[1];
			}
			return new TreeNode[] { ans, p };
		} else {
			return this.findNext(root.right, val, root);
		}
	}

	// 找到key和key的上级
	private TreeNode[] deleteNode(TreeNode me, int key, TreeNode myRoot) {
		if (me == null) {
			return null;
		}
		if (me.val > key) {
			return this.deleteNode(me.left, key, me);
		} else if (me.val < key) {
			return this.deleteNode(me.right, key, me);
		} else {
			return new TreeNode[] { me, myRoot };
		}
	}

	@Override
	public void debug4() {
		this.deleteNode(TreeArray.array2tree(H.str2array4("[3,2,4,1]")), 2);
//		this.deleteNode(TreeArray.array2tree(H.str2array4("[2,0,33,null,1,25,40,null,null,11,31,34,45,10,18,29,32,null,36,43,46,4,null,12,24,26,30,null,null,35,39,42,44,null,48,3,9,null,14,22,null,null,27,null,null,null,null,38,null,41,null,null,null,47,49,null,null,5,null,13,15,21,23,null,28,37,null,null,null,null,null,null,null,null,8,null,null,null,17,19,null,null,null,null,null,null,null,7,null,16,null,null,20,6]")),1);
//		this.deleteNode(TreeArray.array2tree(H.str2array4("[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15]")), 6);
//		[5,3,6,2,4,null,7]
//				3
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
////		[8,4,12,2,6,10,14,1,3,5,7,9,11,13,15]
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
//		Integer num1 = 1000;
//		Integer num2 = 1000;
//		Integer num3 = 100;
//		Integer num4 = 100;
//		System.out.println(num1 == 1000);
//		System.out.println(num1 == num2);
//		System.out.println(num3 == num4);
		String name1 = new String("123");
		String name2 = name1;
		System.out.println(name1 == name2);
		System.out.println(name1.equals(name2));
		System.out.println(name1 == "123");
		System.out.println(name2 == "123");

//		[27,17,33,15,26,32,45,7,16,23,null,31,null,40,49,5,14,null,null,21,25,29,null,34,41,48,null,2,6,10,null,20,22,24,null,28,30,null,39,null,42,46,null,1,4,null,null,9,11,18,null,null,null,null,null,null,null,null,null,37,null,null,44,null,47,0,null,3,null,8,null,null,13,null,19,35,38,43,null,null,null,null,null,null,null,null,null,12,null,null,null,null,36]
//				49
	}

}
